//test.js的代码 ，二叉树的js表示方法
// preorder.js中为遍历的代码。我们的遍历代码都放在里面
const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: null,
  },
};
//用递归进行先序遍历
console.log("先序遍历->");
const preorder = node => {
  // 递归的结束条件
  if (!node) return;
  console.log(node.val);
  //递归的基本结构
  preorder(node.left);
  preorder(node.right);
};
preorder(bt);

console.log("中序遍历->");
const inorder = node => {
  // 递归的结束条件
  if (!node) return;
  //左递归的基本结构
  inorder(node.left);
  console.log(node.val);
  inorder(node.right);
};
inorder(bt);
console.log("后序遍历->");
const postorder = node => {
  // 递归的结束条件
  if (!node) return;
  //左递归的基本结构
  postorder(node.left);
  postorder(node.right);
  console.log(node.val);
};
postorder(bt);
console.log("层序遍历->");
var levelOrder = function (root) {
  if (root === null) return [];
  let result = [];
  let deep = 0;
  recursion(root);

  function recursion(root) {
    deep++;
    if (result[deep - 1]) {
      console.log(root.val);
      result[deep - 1].push(root.val);
    } else result[deep - 1] = [root];
    if (root.left != null) recursion(root.left);
    if (root.right !== null) recursion(root.right);
    deep--;
    return;
  }
  return result;
};
levelOrder(bt);
